home *** CD-ROM | disk | FTP | other *** search
/ Scene Storm / Scene Storm - Volume 1.iso / coding / c / compression_slz / slz_art.txt < prev    next >
Text File  |  1995-11-10  |  37KB  |  879 lines
  1. Simple Compression using an LZ buffer
  2. Part 3 Revision 1.d:
  3. An introduction to compression on the Amiga by Adisak Pochanayon
  4.  
  5. Freely Distributable as long as reproduced completely.
  6. Copyright 1993 Adisak Pochanayon
  7.  
  8. -------------------------------------------------------------------------
  9.      In Part 1 (now obsolete) and Part 2 of the Amiga Compression series,
  10. I covered a new and extremely fast RLE (run-length encoding) method for
  11. graphics.
  12.  
  13.      This article will delve further into the world of compression on
  14. the Amiga by covering my latest experiment in compression techniques and
  15. show the use of a simple LZ history compression algorithm.
  16.  
  17.      In the second part of this article, I describe a Compressor (and
  18. DeCompressor) program in C.  It is not written for optimal speed merely
  19. because I wanted the code to be readable and the time that speed is
  20. really needed is decompression (which occurs in the super-fast assembly
  21. routine).  Using this code along with the unpacker.asm will allow you
  22. to include any raw compressed data easily in your own programs.
  23.  
  24. Important Notes and Disclaimers.
  25.  
  26. NOTE 1:
  27.  
  28.      This is a "beta" document.  I welcome your suggestions but before you
  29.      employ the methods mentioned in this document, please try to realize
  30.      that I hope to provide a completely new compressor within a week or
  31.      two that should be an order of magnitude faster.  I may end up
  32.      slightly changing the compression technique as well to provide
  33.      better compression.  Also, I welcome suggestions to improve the
  34.      "readability" of the article as well.*
  35.  
  36.      *Both of these features have been added.  Hashing with collision
  37.      detection in the compressor, the capability to alter the TAGs easily,
  38.      and a new unpacking algorithm have been added.
  39.  
  40. NOTE 2:
  41.  
  42.      A very common comment that I have received is "Why not use XPK or
  43.      PowerPacker libraries?"  I respond with several reasons.  (I also
  44.      removed a paragraph that some compression library programmers
  45.      found insulting -- Please understand that compression libraries
  46.      are good for the Amiga, but they are not always exactly what a
  47.      programmer wants.)
  48.  
  49.      The first is simply that I wish to provide an alternative method.
  50.      Although, I have been "urged" to let professionals handle compression,
  51.      I would like to argue that any "amateur" can help the field.  My
  52.      compression algorithm has already consistently beat ZOO 2.1 and Arc 5
  53.      for compression ratios and decompression from RAM: to RAM: is
  54.      realistically more than twice as fast as any ZOO encoding.  When
  55.      SLZ is used within a program and compared to ZOO used on the RAM:
  56.      filing system (an unfair test I know), SLZ beats ZOO by a speed
  57.      factor of approximately 15.  So if you feel that a technique that
  58.      achieves better compression than the widely used ZOO and decompresses
  59.      twice as fast is for amateurs, then you might be right.  Then again,
  60.      you might be wrong.  I believe this is a viable "alternative" for
  61.      Amiga programmers.
  62.  
  63.      The second involves distribution: PowerPacker can not be distributed with
  64.      commercial products and it is possible that modules of XPK be likewise
  65.      restricted at the discrimination of their authors.  This algorithm
  66.      is being released as Freely Distributable without restrictions to
  67.      commercial applications although I retain the copyright.  Also, many
  68.      programmers would rather have direct control over their data and not
  69.      go through the overhead of a library, regardless of how small that
  70.      overhead is.
  71.  
  72.      Another factor, of course, is speed.  SLZ has one of the fastest LZ
  73.      unpacking algorithms available.  This is in part due to the very
  74.      little overhead imposed on the routine.  The original asm encoding
  75.      plus the enhancements made by Jesse Michael play no small role in
  76.      the speed factor though.  Combine that with the simple yet elegant
  77.      data format and you get some awesome speed.  To quote U.D. Mueller,
  78.      "Good implementations of the algorithm used by ZOO are about
  79.      an estimated half as fast as yours (check xpkBLZW)."  So if you want
  80.      TWICE the speed, drop ZOO -- go SLZ.
  81.  
  82.      The final reason is even if you decide not to use SLZ, I hope this
  83.      article provides an educational benefit to Amiga programmers.  I have
  84.      certainly learned a lot by my experiments in data compression.  There
  85.      is so little "public" information on data compression available even if
  86.      you read the compression newsgroups.  I have also seen several postings
  87.      on the c.s.a.p. newsgroup recently requesting further information on
  88.      compression algorithms.  With the large positive response I got on the
  89.      RLE compression article earlier this year, I thought that an LZ
  90.      article might also be received positively.
  91.  
  92. NOTE 3:
  93.  
  94.      I have been told by several people that the compression algorithm I
  95.      created is almost identical to the LZRW algorithm (partially patented).
  96.      One person even sent me the specs of LZRW by e-mail.  Indeed, the
  97.      two algorithms are similar.  However, there are some distinct
  98.      differences.  SLZ attains better compression than LZRW by using
  99.      exhaustive history searching.  SLZ also now uses a 16 collision
  100.      HASHING for compression compared to the unit HASH used by LZRW.
  101.      Furthermore, SLZ codes compressed strings slightly different, both
  102.      with the END-TAGs, and the compressed string length.  By doing so,
  103.      SLZ again allows better compression (with a 4096-byte history,
  104.      SLZ allows string lengths to vary between 3 and 17 while LZRW
  105.      has a maximum of 15).  Due to the data representation differences
  106.      and the differences in the actual compression method, SLZ will
  107.      *ALWAYS* obtain better compression ratios than LZRW.  And yet another
  108.      difference is the ability to alter the TAG in SLZ such that a
  109.      2048 History and 33-byte maxstring can be achieved.  Finally, SLZ has
  110.      a (currently) faster decompression algorithm than LZRW.  Because of
  111.      all these differences, I warrant that SLZ is a new algorithm that
  112.      is simply in the same family as LZRW (After all I did say it is an
  113.      LZ compression routine).
  114.  
  115.      I don't believe I have violated any patents with SLZ or broken any
  116.      copyrights as I genuinely came up with this idea on my own.  If
  117.      I had access to other good compression source codes, I wouldn't have
  118.      written SLZ to begin with.  However, if I am violating any such
  119.      ownership of intellectual property, I will remove SLZ from Freely
  120.      Distributable status and I will ask anyone who has a copy of this
  121.      article to destroy it and forbid my code from being used for any
  122.      purposes on the Amiga.
  123.  
  124.  
  125.   Comments, questions, spelling errors, or grammar police?  Let me know :)
  126.  
  127. Improvements from 3.0a:
  128.      I have more than doubled the speed of compression on text and many
  129.      other forms of data by modifying my HASH code to allow for up to
  130.      16 HASH collisions to be detected before brute force exhaustive
  131.      searching occurs.  Users who do not use the hash option will not
  132.      notice the speedup in the C routines.
  133.      
  134.      I have also made the files more flexible to modify the TAG/CS
  135.      bit-orderings.  This will allow users to customize the file for
  136.      greater compression by trading off length of compression strings
  137.      for length of compression history.  I have found that a history
  138.      of 2048 instead of 4096 works much better for many graphics images
  139.      which have lots of "line" oriented repeats.  This allows me to
  140.      compress longer repeat strings with a single CS tag.
  141.  
  142.      Many thanks to Jesse Michael of Haze of Epsilon (jdm@key880.rain.com),
  143.      for rewriting the assembly.   He unrolled my loops, freed a register,
  144.      restructured my branching, optimized literal copying by making the
  145.      speed of copying literal strings up to three times faster (on a 68000).
  146.      Basically, he built a Porsche out of VW parts (joke - the original
  147.      Porsches were built with VW parts :).  The asm code is similar to
  148.      the original (same excellent comments) and still easy to read.  The
  149.      asm takes a little more space, but the emphasis of this compressor
  150.      has always been the speed of decompression.
  151.  
  152.      Thanks also go out to Urban Dominik Mueller (UDM) for pointing out some
  153.      mistakes I made in my previous article and allowing me to correct them.
  154.      Also, thank you for pointing out some obvious optimizations that I had
  155.      not implemented such as unrolled loops.
  156.  
  157.      Finally, thanks to the 7-8 other people who responded with interesting
  158.      suggestions and to the person who sent me the SPECs on the similar
  159.      LZRW algorithm.
  160.  
  161. Disclaimer:
  162.  
  163.      Neither Adisak Pochanayon, nor SilverFox SoftWare, warrant the use
  164.      of this article for any means.  The author holds no responsibility
  165.      to the accuracy of the description of the routines or any adverse
  166.      side effects they may cause when used on any machine.
  167.  
  168. -------------------------------------------------------------------------
  169.  
  170. Adisak Pochanayon
  171. 2525 University Avenue Apt #J
  172. Madison WI 53706
  173. 608-238-2463
  174. pochanay@cae.wisc.edu
  175.  
  176.      So you've plugged in your RLE compressor from Parts 1 and 2 and found
  177. that including fast compressed graphics is really easy to do in programs.
  178. But you want to include help text or other data that isn't easily compressed
  179. by RLE methods.  You don't want to give up the incredible speed from straight
  180. RLE yet you want better compression.
  181.  
  182.      One simple solution might be to use one of the fine compression
  183. libraries available on the Amiga.  However, this isn't always the best
  184. solution.  Some libraries restrict commercial distribution, other libraries
  185. don't provide source code, and still others require you allocate complicated
  186. buffers and handles before using them.  None of them guarantee to work
  187. if you have shut down the OS, multi-tasking or are using nonstandard
  188. programming methods (not that I would ever advocate OS shutdowns). Even
  189. libraries that are simple to use are not always tolerant to "braindead"
  190. installation.  If a library is missing, or a wrong revision, your program
  191. won't run -- or worse, it could crash the machine.
  192.  
  193.      For a beginning or intermediate programmer, the "best" solution might
  194. be the simplest solution.  Using a very simple, compact routine that can
  195. easily be linked or added to programs and used without worrying about
  196. opening libraries, looking for include files, allocating buffers, or any
  197. other overhead.  However, to be viable, the routine would have to feature
  198. very fast decompression and have full available source for any custom
  199. modifications that a more experienced programmer might wish to make.
  200. Before deciding on an exact format for the compression, a programmer might
  201. want to examine the available algorithms.
  202.  
  203.      RLE, or run-length encoding is great for graphics where you have many
  204. repeating bytes of data.  That's why it was chosen as part of the IFF
  205. standard.  However, RLE's compression of this article would be feeble at best
  206. and the performance would be noticeably poorer than ZOO, ARC, or LHA.
  207. RLE's biggest advantage is it's extremely fast speed (Described in Part
  208. 2 of this series).
  209.  
  210.      A better method might be to reduce the "size" of codes for ASCII
  211. characters that appear often (e,r,o,s,t,l,etc.) and increase the "size" of
  212. codes that do not appear often (z,q,x,etc.).  Think of it as making the size
  213. of codes for the ASCII characters related to their SCRABBLE (tm) scores.
  214. This type of compression, which is known as HUFFMAN codes, is much better at
  215. compressing text than RLE methods.  Unfortunately, using huffman-coding or
  216. huffman variants can often be too slow for games or other programs that
  217. require extrememly fast decompression.  HUFFMAN coding also requires creation
  218. and maintainance of structures to describe the codes that can become quite
  219. confusing.  By varying the codes as one traverses through a file, the
  220. compression can be improved even more at a cost of greater file complexity.
  221. This is known as ADAPTIVE HUFFMAN compression.
  222.  
  223.      Another method of compression is what is often called LZ (Lempel-Ziv)
  224. compression.  This involves a "history" of some sort representing the last
  225. X characters read and a pointer to a current character buffer that has
  226. yet to be compressed.  The compression program looks for strings matching
  227. the current string in the history and replaces matches with a data TAG
  228. which describes the offset and length of the data in the history buffer.
  229. This is the type of compression that will be discussed in this article.
  230.  
  231. Important note from (UDM):  This actually describes the LZ77 group of LZ's.
  232. "There are other algorithms in the LZ family (like LZ78/LZW as used in
  233. 'compress') that work totally different."
  234.  
  235.      Slightly more complicated is a compression called LZH or LZ-Huffman
  236. compression.  LZH (or LH) often outperforms LZ.  This combines the LZ
  237. compression with HUFFMAN encoding methods.  Adaptive LZH is even more
  238. complicated, but again can lead to better compression.  Adaptive LZH is
  239. not always better as LhA uses static Huffman codes and usually outperforms
  240. LhArc which uses dynamic adaptive encoding (UDM).  However, these methods
  241. of compression are outside the scope of this article which is directed
  242. mainly towards intermediate programmers.
  243.  
  244.      So which method is best?  Well, I planned on including text, graphics,
  245. and other files in programs, with an emphasis on EXTREMELY FAST unpacking
  246. of compressed data.  After examining all the methods available to me, I
  247. decided that the most flexible algorithm with enough speed would be a byte
  248. oriented LZ compression method.  I decided to eliminate CRCs (checks on the
  249. integrity of the data) since the data would be "included" within a program
  250. and data integrity is most often a problem during telecommunications
  251. where a program would normally be transfered as part of a "LZH" or "ZOO"
  252. archive.  I also eliminated bounds checking since from a programming
  253. perspective, I will always know the bounds of the data or I can include
  254. a simple structure to describe the size of the data without adding to the
  255. complexity of the compressed data itself.
  256.  
  257.      These ideas led to my creation of a simple LZ compression method that
  258. I call SLZ (version 0).  After writing programs to implement my new
  259. compression technique, I found that compression was comparable to ZOO (v2.1)
  260. and ARC (v5.0).  As a matter of fact, on the Fred Fish Library Contents-870,
  261. a 1,451,420 byte text, SLZ-0 outperformed ZOO by over 34K and ARC by over
  262. 40K !!!!  Compression times for the SLZ-0 program are considerably longer
  263. than similar compression times with ZOO however (the code is not optimized
  264. at all and features exhaustive searching in C which is excruciatingly slow).
  265. However, using the asm decompression routines from within a program yielded
  266. decompression at a level of speed about 15 times the speed of ZOO from the
  267. RAM: disk!!!  (Please see Note 2 for more on this claim).
  268.  
  269.      Part of this incredible decompression speed comes from the simplicity
  270. of the encoding method.  SLZ-0 works on a TAG-data format.  First, an 8-bit
  271. TAG is read which describes the next 8 chunks of data to follow.  For each
  272. chunk in the data, a bit in the TAG will be set or cleared.  A set bit
  273. represents compressed data and a cleared bit represents uncompressed data.
  274. each time a cleared bit is encountered, the unpacker simply copies a byte
  275. from source to destination and continues on to the next chunk.  When a set
  276. bit is encountered in the tag, the unpacker reads a byte from the source.
  277. If this byte is zero, the routine exits.  Otherwise, a second byte is
  278. read.  The combination of these two bytes yields the location and length
  279. of the data to copy in the following form (O is offset - L is length):
  280.  
  281.         O11 O10 O9 O8 L3 L2 L1 L0     O7 O6 O5 O4 O3 O2 O1 O0    H=4096
  282.  
  283. The location of the data is determined by subtracting the offset from the
  284. current output buffer pointer (as compressed bytes are copied from output
  285. to output and not input to output).  The length is simply the value
  286. represented plus two.
  287.  
  288.      The compressor and decompression routine allow you to easily modify
  289. the TAG format by changine #defines/EQU's to allow for a choice of
  290. History=4096 bytes/MaxString=17 or History=2048 bytes/MaxString=33.
  291. The normal default (I found it to be generally better on everything but
  292. bitmapped graphics which have long repeat strings), is a History=4096.
  293. Changing to History=2048 results in the following CS TAG.
  294.  
  295.          O10 O9 O8 L5 L3 L2 L1 L0     O7 O6 O5 O4 O3 O2 O1 O0    H=2048
  296.  
  297. Again, the location of the data is determined by subtracting the offset from the
  298. current output buffer pointer (as compressed bytes are copied from output
  299. to output and not input to output) and the length is simply the value
  300. represented plus two.  However, if you change the compression, be sure to
  301. be careful to call the correct decompression routine.
  302.  
  303.      Believe it or not, this simple compression scheme yields compression
  304. ratios similar to ZOO and decompression speeds that are several times
  305. faster.  A simple asm implementation of the unpacker is provided for use in
  306. programs which include SLZ-0 compressed data.  To include compressed data
  307. in a file, simply compress it with the compressor and use a directive such
  308. as INCBIN from the CAPE 68K assembler to include the data.  Then call this
  309. routine from C or ASM with the source and destination pointers.  It's as
  310. easy as folling off a log :)
  311.  
  312.      Here's the asm (highly documented for non-asm programmers).
  313.  
  314. ---------------------------BEGIN ASM----------------------------------------
  315.          CODE, PUBLIC
  316.  
  317. *****    VOID __regargs UnPackSLZ(UBYTE *from, UBYTE *to)
  318. *****        calling from assembly:      a0   ,       a1
  319.  
  320. *****    This code takes a SLZ packed buffer and unpacks it to
  321. *****  another buffer.  Note: for maximum speed, no checking of any
  322. *****  sort is performed for boundaries.  Also, there is no CRC or
  323. *****  error correction/detection.  It is assumed that your data is
  324. *****  valid.
  325.  
  326. *****  Uncomment the following for use with C without __regargs.
  327. *****
  328. *****             XDEF _UnPackSLZ
  329. *****    _UnPackSLZ:
  330. *****             movea.l  4(SP),a0
  331. *****             movea.l  8(SP),a1
  332.  
  333. *****     CS_MASK=(2^(8-CS_LSL))-1
  334. *****     CS_LSL increases with history size (4->H=4096)
  335. CS_MASK   EQU  15
  336. CS_LSL    EQU  4
  337.  
  338.          XDEF @UnPackSLZ
  339. @UnPackSLZ:
  340.  
  341.             movem.l d2-d3/a2,-(SP)  ; Save Registers
  342.  
  343.             bra.b   slz_start       ; Skip to entry point
  344.  
  345. slz_literal move.b  (a0)+,(a1)+     ; Copy 8 byte literal string FAST!
  346.             move.b  (a0)+,(a1)+
  347.             move.b  (a0)+,(a1)+
  348.             move.b  (a0)+,(a1)+
  349.             move.b  (a0)+,(a1)+
  350.             move.b  (a0)+,(a1)+
  351.             move.b  (a0)+,(a1)+
  352.             move.b  (a0)+,(a1)+
  353.  
  354. slz_start   move.b  (a0)+,d0        ; Load compression TAG
  355.             beq.b   slz_literal     ; 8-byte literal string?
  356.  
  357.             moveq   #7,d1           ; Loop thru 8 bits
  358. slz_nxtloop add.b   d0,d0           ; Set flags for this compression TAG
  359.             bcs.b   slz_comp        ; If bit is set then compress
  360.             move.b  (a0)+,(a1)+     ; Otherwise copy a literal byte
  361.             dbf     d1,slz_nxtloop  ; Check and loop through 8 iterations
  362.             bra.b   slz_start       ; Get next TAG
  363.  
  364. slz_comp    moveq   #0,d2           ; Clear offset register
  365.             move.b  (a0)+,d2        ; Load compression specifier (cs) into d2
  366.             beq.b   slz_exit        ; If cs is 0, exit (decompression finished)
  367.             moveq   #CS_MASK,d3     ; Copy cs into number reg and mask off bits
  368.             and.w   d2,d3           ;   num = ( cs & CS_MASK ) [+ 2] ; {at least 3}
  369.             lsl.w   #CS_LSL,d2      ; Multiply cs_or by (2^CS_LSL)
  370.             move.b  (a0)+,d2        ;   and replace lsb with rest of cs
  371.             movea.l a1,a2           ; Now compute the offset from the current
  372.             suba.w  d2,a2           ;   output pointer (d2 auto-extends)
  373.  
  374.             add.w   d3,d3           ; Compute the unroll offset and begin
  375.             neg.w   d3              ;   unrolled compressed data expansion
  376.             jmp     slz_unroll(pc,d3.w)
  377.  
  378. slz_exit    movem.l (SP)+,d2-d3/a2  ; Restore Registers
  379.             rts                     ; EXIT routine
  380.  
  381. ****
  382. **** The following is an unrolled loop for compressed data copying.
  383. **** The first part of the loop (lines ;33 - ;18) are not necessary
  384. **** unless you have specified a history of size 2048 and made the
  385. **** apropriate changes to SLZ.c as well.
  386. ****
  387.  
  388. **** For when H=2048
  389.             move.b  (a2)+,(a1)+     ; 33
  390.             move.b  (a2)+,(a1)+     ; 32
  391.             move.b  (a2)+,(a1)+     ; 31
  392.             move.b  (a2)+,(a1)+     ; 30
  393.             move.b  (a2)+,(a1)+     ; 29
  394.             move.b  (a2)+,(a1)+     ; 28
  395.             move.b  (a2)+,(a1)+     ; 27
  396.             move.b  (a2)+,(a1)+     ; 26
  397.             move.b  (a2)+,(a1)+     ; 25
  398.             move.b  (a2)+,(a1)+     ; 24
  399.             move.b  (a2)+,(a1)+     ; 23
  400.             move.b  (a2)+,(a1)+     ; 22
  401.             move.b  (a2)+,(a1)+     ; 21
  402.             move.b  (a2)+,(a1)+     ; 20
  403.             move.b  (a2)+,(a1)+     ; 19
  404.             move.b  (a2)+,(a1)+     ; 18
  405.  
  406. **** For when H=4096 do not include the above (18-35)
  407.             move.b  (a2)+,(a1)+     ; 17
  408.             move.b  (a2)+,(a1)+     ; 16
  409.             move.b  (a2)+,(a1)+     ; 15
  410.             move.b  (a2)+,(a1)+     ; 14
  411.             move.b  (a2)+,(a1)+     ; 13
  412.             move.b  (a2)+,(a1)+     ; 12
  413.             move.b  (a2)+,(a1)+     ; 11
  414.             move.b  (a2)+,(a1)+     ; 10
  415.             move.b  (a2)+,(a1)+     ;  9
  416.             move.b  (a2)+,(a1)+     ;  8
  417.             move.b  (a2)+,(a1)+     ;  7
  418.             move.b  (a2)+,(a1)+     ;  6
  419.             move.b  (a2)+,(a1)+     ;  5
  420.             move.b  (a2)+,(a1)+     ;  4
  421.             move.b  (a2)+,(a1)+     ;  3
  422. slz_unroll  move.b  (a2)+,(a1)+     ;  2
  423.             move.b  (a2)+,(a1)+     ;  1
  424.  
  425.             dbf     d1,slz_nxtloop  ; Check and loop through 8 iterations
  426.             bra.s   slz_start       ; Process Next TAG
  427.  
  428.      END
  429. ---------------------------END ASM------------------------------------------
  430.  
  431.      The compressor/decompressor program in C is mainly a utility to compress
  432. data for use by this high speed assembly unpacker.  In general the program
  433. applies a brute force method for matching strings within the history and
  434. provides extremely slow compression.  Decompression, however, is rather
  435. fast even within the C environment and using a file system.
  436.  
  437.      Even though the exhaustive searching is what leads to compression on
  438. par with ZOO (often better), it's painful in C.  However, I didn't want to
  439. write this in asm as the code is currently very portable from machine to
  440. machine and it's much harder for intermediate programmers to read asm.
  441.  
  442.      I have made some improvements to the C utility to improve compression
  443. speeds though.  By defining the symbol "hashing_on", the program will
  444. allocate a 256K HASH table that is used for quickly matching strings and
  445. performing up to 16 collision checks based on the first two bytes of
  446. the current string.  After these checks have been made, the program resorts
  447. to exhaustively scanning the rest of the history buffer.  However, the
  448. hash table does more than double the speed of the compression.  Even with
  449. the hashing on, compression can take a while but you'll be rewarded with
  450. the high speed at which your data can be decompressed.
  451.  
  452.      The compressor works quite simply.  First, it examines the string in
  453. the input file that is currently being pointed to.  If the hashing option is
  454. present, the program checks hashed pointers for matching strings.  It then
  455. searches the remainder of the history buffer exhaustively for matches of
  456. length greater than two.  When it finds a string longer than the current
  457. best match, the current best match is updated.  If a string of the maximum
  458. compressed string length is found, the searching is halted.  As long as
  459. a string of length greater than two is found, the compressor sets a bit
  460. in the TAG and creates a CS specifier which contains data with the offset
  461. and length of the compressed sctring for the output file.  Otherwise, no
  462. bit in the TAG is set and a single literal byte is copied to the output.
  463. The program continues until the input is exhausted.  When the input is
  464. exhausted, the program sets a bit in the TAG and writes a zero (byte) to the
  465. output signifying it has finished compression.
  466.  
  467.      An interesting aspect of this compression technique is how much data
  468. remains "intact" from input file to output file.  When looking at the output
  469. of most compression programs, a human will see nothing but jibberish.  The
  470. output of a text file compressed with SLZ will still look partially
  471. intelligible to a human and can be hand-decoded much more easily.
  472.  
  473.      The decompression is simply a C version of the asm decompressor (the
  474. asm was actually written first) that is file oriented in it's output.  It
  475. is robust but lacks optimization.  This is OK though because it is still
  476. rather fast (extremely fast compared to compression).
  477.  
  478.      If anyone writes a faster version of this program (very easy to do since
  479. I have made few optimizations and the program is more "robust" in error
  480. handling than "efficient" in speed), please let me know.  I plan on writing
  481. a faster version myself when I have the time but finding the time to write
  482. a ~40K article is hard enough.
  483.  
  484. The program is used with the following syntax: SLZ (u or p) arg_src arg_dest
  485.  
  486.                SLZ  FLAG  SOURCE  DESTINATION
  487.                FLAG can be U - unpack  P - pack
  488.  
  489.  
  490. ---------------------------BEGIN C------------------------------------------
  491. ;/* SLZ.c - SLZ (un)packer -- Source for Lattice/SAS C version 5.10
  492.  
  493. LC -rr -b1 -ccist -v -O -L  SLZ.c
  494. quit
  495.  
  496. */
  497.  
  498. /*****************************************************************************
  499.      SLZ - SLZ (un)packer.            C. 1993 SilverFox SoftWare.
  500.         Written by Adisak Pochanayon     All Rights Reserved.
  501.  
  502.           This program is a simple example of using SLZ compression
  503.      upon a file.  It will allow you to both pack and unpack a file
  504.      using SLZ compression.  The syntax for calling this program from
  505.      the CLI is:
  506.  
  507.                SLZ  FLAG  SOURCE  DESTINATION
  508.                FLAG can be U - unpack  P - pack
  509.  
  510. *****************************************************************************/
  511.  
  512. // Comment out the following line to save 256K of memory but can slow down
  513. //   compression (immensely :( ).
  514. #define hashing_on
  515.  
  516. #include  <stdio.h>
  517. #include  <stdlib.h>
  518.  
  519. /*  defines for interpreting the CLI arguments    */
  520. #define   arg_flag     1
  521. #define   arg_srce     2
  522. #define   arg_dest     3
  523. #define   arg_count    4
  524.  
  525. /*  defines for handling argument and file errors */
  526. #define   slz_error   1024
  527. #define   error_read   0
  528. #define   error_args   1
  529. #define   error_srce   2
  530. #define   error_dest   4
  531. #define   error_write  8
  532.  
  533. /*  defines for file compression / decompression  */
  534. #define   FILE_ERROR   0
  535. #define   TRUE         1
  536. #define   FALSE        0
  537.  
  538. /*** GLOBAL VARIABLE FOR ERRORS AND FILES ***/
  539. int  error=0;
  540. long length;
  541. short lzhist_offset=0;
  542.  
  543. /*
  544.  * SHIFT_UPPER is amount to multiply upper in one byte to get into next
  545.  *   higher byte. (H=4096 -> 16, H=2048 -> 8)
  546.  * LSR_upper is amount to shift codeword to get upper byte into lower byte.
  547.  *   (H=4096 -> 4, H=2048 -> 3)
  548.  * MAX_COMP_LENGTH = (2 ^ (8-LSR_upper)) + 1
  549.  */
  550.  
  551. #define HISTORY_SIZE     4096
  552. #define MASK_history     (HISTORY_SIZE-1)
  553. #define MASK_upper       (0xF0)
  554. #define MASK_lower       (0x0F)
  555. #define SHIFT_UPPER      16
  556. #define LSR_upper        4
  557. #define MAX_COMP_LEN     17
  558.  
  559. unsigned char LZ_history[HISTORY_SIZE];
  560. #ifdef hashing_on
  561. long far HASH_TABLE[65536];
  562. #define CHASH(a,b,c)  ( ((((a&63)<<6)+(b&63))<<4)+c )
  563. #endif
  564.  
  565. void writechar(register unsigned char outchar, register FILE *outfile)
  566. {
  567.   if (putc(outchar,outfile)==EOF)
  568.     {
  569.       printf("Error writing output file.\n");
  570.       fcloseall();
  571.       exit(slz_error + error_write);
  572.     }
  573.   LZ_history[lzhist_offset]=outchar; lzhist_offset=(lzhist_offset+1)&MASK_history;
  574. }
  575.  
  576. void UnPackSLZ(unsigned char *inbuffer, register FILE *outfile)
  577. {
  578.   short myTAG, mycount, myoffset;
  579.   long int loop1;
  580.  
  581.   for(;;)  // loop forever (until goto occurs to break out of loop)
  582.     {
  583.       myTAG=*inbuffer++;
  584.       for(loop1=0;(loop1!=8);loop1++)
  585.         {
  586.           if(myTAG&0x80)
  587.             {
  588.               if((mycount=*inbuffer++)==0)  // Check EXIT
  589.                 { goto skip2; } // goto's are gross but it's efficient :(
  590.               else
  591.                 {
  592.                   myoffset=HISTORY_SIZE-(((MASK_upper&mycount)*SHIFT_UPPER)+(*inbuffer++));
  593.                   mycount&=MASK_lower;
  594.                   mycount+=2;
  595.                   while(mycount!=0)
  596.                     {
  597.                       writechar(LZ_history[(lzhist_offset+myoffset)&MASK_history],outfile);
  598.                       mycount--;
  599.                     }
  600.                 }
  601.             }
  602.           else
  603.             { writechar(*inbuffer++,outfile); }
  604.           myTAG+=myTAG;
  605.         }
  606.     }
  607. skip2:
  608.   return;
  609. }
  610.  
  611. #ifdef hashing_on
  612. void ADDHASH(long a,long b, long c)
  613. {
  614.   long *INHASH,*BEFINHASH;
  615.   INHASH=&HASH_TABLE[CHASH(a,b,15)];
  616.   BEFINHASH=INHASH-1;
  617.   *(INHASH--)=*(BEFINHASH--); *(INHASH--)=*(BEFINHASH--); *(INHASH--)=*(BEFINHASH--);
  618.   *(INHASH--)=*(BEFINHASH--); *(INHASH--)=*(BEFINHASH--); *(INHASH--)=*(BEFINHASH--);
  619.   *(INHASH--)=*(BEFINHASH--); *(INHASH--)=*(BEFINHASH--); *(INHASH--)=*(BEFINHASH--);
  620.   *(INHASH--)=*(BEFINHASH--); *(INHASH--)=*(BEFINHASH--); *(INHASH--)=*(BEFINHASH--);
  621.   *(INHASH--)=*(BEFINHASH--); *(INHASH--)=*(BEFINHASH--); *(INHASH)=*(BEFINHASH);
  622.   *BEFINHASH=c;  
  623. }
  624. #endif
  625.  
  626. void PackSLZ(unsigned char *inbuffer, register FILE *outfile)
  627. {
  628.   long int loop1,loop2, startvalue, endvalue, wherefound;
  629.   unsigned char outchars[MAX_COMP_LEN*10];
  630.   unsigned char *a_buffer, *b_buffer;
  631.   short lenoutchars;
  632.   short myTAG, iter;
  633.   short done,found,temp;
  634.  
  635. #ifdef hashing_on
  636.   long *INHASH;
  637.   short HASHCHECK;
  638.  
  639.   for(loop1=0;loop1!=65536;loop1++)
  640.     {
  641.       HASH_TABLE[loop1]=-1;
  642.     }
  643.   HASH_TABLE[CHASH(inbuffer[0],inbuffer[1],0)]=0;
  644. #endif
  645.  
  646.   loop1=1; loop2=length-1; iter=1;  // Always do a literal first byte
  647.   outchars[1]=inbuffer[0]; lenoutchars=2;
  648.   done=FALSE;
  649.  
  650.   while(! done)
  651.     {
  652.       myTAG=0;
  653.       while((iter<8)&&(! done))
  654.         {
  655.  
  656. /***--- This is the slowest part.  I should rewrite it in ASM ---***/
  657.  
  658.           startvalue=loop1-MASK_history;
  659.           if (startvalue<0) startvalue=0;
  660.           found=0;
  661.  
  662. #ifdef hashing_on
  663.           INHASH=&HASH_TABLE[CHASH(inbuffer[loop1],inbuffer[loop1+1],0)];
  664.           HASHCHECK=16; // Scan for matches in HASH TABLE
  665.           while((HASHCHECK)&&((endvalue=*INHASH++)>=startvalue))
  666.             {
  667.               temp=0;
  668.               a_buffer=&inbuffer[loop1];
  669.               b_buffer=&inbuffer[endvalue];
  670.               while((*(a_buffer++) == *(b_buffer++))&&(temp<MAX_COMP_LEN))
  671.                 {
  672.                   temp++;
  673.                 }
  674.               if(found<temp)
  675.                 {
  676.                   if ((temp+loop1)>length)
  677.                     {
  678.                       temp=length-loop1;
  679.                       if(found<temp)
  680.                         {
  681.                           found=temp;
  682.                           wherefound=endvalue;
  683.                         }
  684.                     }
  685.                   else
  686.                     {
  687.                       found=temp;
  688.                       wherefound=endvalue;
  689.                     }
  690.                   if (found==MAX_COMP_LEN) { goto skip1; }
  691.                 }
  692.               HASHCHECK--;
  693.             }
  694. #else
  695.           endvalue=loop1-1;
  696. #endif
  697.  
  698.           while(endvalue>=startvalue) // Scan for matches
  699.             {
  700.               temp=0;
  701.               a_buffer=&inbuffer[loop1];
  702.               b_buffer=&inbuffer[endvalue];
  703.               while((*(a_buffer++) == *(b_buffer++))&&(temp<MAX_COMP_LEN))
  704.                 {
  705.                   temp++;
  706.                 }
  707.               if(found<temp)
  708.                 {
  709.                   if ((temp+loop1)>length)
  710.                     {
  711.                       temp=length-loop1;
  712.                       if(found<temp)
  713.                         {
  714.                           found=temp;
  715.                           wherefound=endvalue;
  716.                         }
  717.                     }
  718.                   else
  719.                     {
  720.                       found=temp;
  721.                       wherefound=endvalue;
  722.                     }
  723.                   if (found==MAX_COMP_LEN) { goto skip1; }
  724.                 }
  725.               endvalue--;
  726.             }
  727. skip1:
  728.  
  729. /***--- End of *SLOW* exhaustive history scan :( WHEW! ---***/
  730.  
  731.  
  732.           if(found>2) // Compression will now occur
  733.             {
  734.               myTAG|=(128>>iter);
  735.               endvalue=loop1-wherefound;
  736.               startvalue=((endvalue>>LSR_upper)&MASK_upper)+(found-2);
  737.               outchars[lenoutchars++]=startvalue;
  738.               outchars[lenoutchars++]=(unsigned char)endvalue;
  739.               loop2-=found;
  740.               while(found!=0)
  741.                 {
  742. #ifdef hashing_on
  743.                  ADDHASH(inbuffer[loop1],inbuffer[loop1+1],loop1);
  744. #endif
  745.                   loop1++; found--;
  746.                 }
  747.             }
  748.           else // No Compression, copy literal byte
  749.             {
  750. #ifdef hashing_on
  751.               ADDHASH(inbuffer[loop1],inbuffer[loop1+1],loop1);
  752. #endif
  753.               outchars[lenoutchars++]=inbuffer[loop1++];
  754.               loop2--;
  755.             }
  756.           if(loop2<=0)
  757.             {
  758.               done=TRUE;
  759.               if(loop2<0)
  760.                 {
  761.                   printf("HMMM... ooops!!!\n");
  762.                 }
  763.             }
  764.           iter++;
  765.         }
  766.       if(! done)
  767.         {
  768.           outchars[0]=myTAG;
  769.           for(startvalue=0;startvalue!=lenoutchars;startvalue++)          
  770.             {
  771. //            writechar(outchars[startvalue],outfile);
  772. /*****/
  773.   if (putc(outchars[startvalue],outfile)==EOF)
  774.     {
  775.       printf("Error writing output file.\n");
  776.       fcloseall();
  777.       exit(slz_error + error_write);
  778.     }
  779. /*****/
  780.  
  781.             }
  782.           lenoutchars=1;
  783.           iter=0;
  784.         }
  785.     }
  786.   if(iter==8)
  787.     {
  788.       outchars[0]=myTAG;
  789.       for(startvalue=0;startvalue!=lenoutchars;startvalue++)          
  790.         {
  791.           writechar(outchars[startvalue],outfile);
  792.         }
  793.       writechar(255,outfile); writechar(0,outfile);
  794.     }
  795.   else
  796.     {
  797.       outchars[0]=myTAG|(128>>iter);
  798.       for(startvalue=0;startvalue!=lenoutchars;startvalue++)          
  799.         {
  800.           writechar(outchars[startvalue],outfile);
  801.         }
  802.       writechar(0,outfile);
  803.     }
  804. }
  805.  
  806. main(int argc, char *argv[])
  807. {
  808.   FILE *infile, *outfile;
  809.   unsigned char *inbuffer;
  810.  
  811.   printf(" SLZ -- SLZ (un)packer.          C. 1993 SilverFox SoftWare.\n");
  812.   printf("   Written by Adisak Pochanayon     All Rights Reserved.\n\n");
  813.  
  814.   if (argc != arg_count)
  815.     {
  816.       error= slz_error + error_args;
  817.       printf("Error -- Please check arguments.\n");
  818.     }
  819.   else if ((infile  = fopen(argv[arg_srce],"r"))==FILE_ERROR) 
  820.     {
  821.       error= slz_error + error_srce;
  822.       printf("Error -- SOURCE file could not be opened.\n");
  823.     }
  824.   else if ((outfile = fopen(argv[arg_dest],"w"))==FILE_ERROR)
  825.     {
  826.       error= slz_error + error_dest;
  827.       printf("Error -- DESTINATION file could not be opened.\n");
  828.     }
  829.   else
  830.     {
  831. /*
  832.  * Get the length of the input file (sorry it takes me 3 calls :( )
  833.  * If you have a better way, let me know.
  834.  */
  835.       fseek(infile,0,2); length=ftell(infile); rewind(infile);
  836.  
  837.       if (length>2) if ((inbuffer=(unsigned char *)getml(length))!=0)
  838.         {
  839.           fread(inbuffer,1,length,infile);  // assume this goes no problem :)
  840.           switch (*argv[arg_flag])
  841.             {
  842.               case 'U' : case 'u' : printf("UnPacking File %s.\n",argv[arg_srce]);
  843.                          UnPackSLZ(inbuffer, outfile); break;
  844.               case 'P' : case 'p' : printf("Packing File %s.\n",argv[arg_srce]); 
  845.                          PackSLZ(inbuffer, outfile);   break;
  846.               default  : error=slz_error + error_args; printf("Error -- no FLAG selected.\n");
  847.             }
  848.           rlsml(inbuffer,length);
  849.         }
  850.     }
  851.  
  852.   if (error!=0)
  853.      printf("\nSLZ command syntax is:  \"SLZ  FLAG  SOURCE  DESTINATION\"\n   where FLAG can be U - unpack  P - pack.\n\n");
  854.   else
  855.      printf("\nSLZ successfully completed\n");
  856.  
  857.   fcloseall();
  858.   exit(error);
  859. }
  860. -----------------------------END C------------------------------------------
  861.  
  862. I achieved compression to 44.07% by applying SLZ to this text file.
  863. This is better than ZOO by almost 1,000 bytes!
  864. (0%=impossibly good - 100+%=really bad).
  865.  
  866. -----------------------------------------------------------------------
  867.  
  868.      As usual, I invite any questions or comments.  Please feel free
  869. to e-mail me at pochanay@cae.wisc.edu for more indepth discussions.
  870. I am still looking for Amiga Artists to help with new games and
  871. programs I am planning on writing.  (Music, graphics, etc).
  872.  
  873.      Also, if you're a commercial developer interested in exploiting
  874. my programming skills..... :)
  875.  
  876. Adisak Pochanayon
  877. SilverFox SoftWare
  878. pochanay@cae.wisc.edu
  879.